Ternary content-addressable memory (TCAM) is a type of associative memory hardware device comprising a table of fixed-width TCAM entries. Each entry consists of W symbols, taking on the ternary alphabet {“0”, “1”, “*”}. {“0”, “1”} are proper bit values, while “*” stands for “don't-care.” The entry width of contemporary TCAM devices is typically configurable to a width of 72, 144, 288 or 576 symbols. The size (i.e. the number of TCAM entries) of contemporary TCAMs is orders-of-magnitude larger than their width: Current TCAMs, for example, can store, in a single device, more than 128K ternary entries that are 144 bits wide.
TCAM enables parallel matching of a key against all entries and thus provides high throughput that is unparalleled by software-based (or SRAM-based) matching solutions. The input to the TCAM is a ternary word of length W called a search key. Search key u matches entry v if the proper bits of u agree with those of v. The basic function of a TCAM is to simultaneously compare a search key with all TCAM entries in parallel. The index returned by the lookup operation is computed by a TCAM module called a match-line (ML) encoder. If there is a single matching TCAM entry, its index is output by the ML encoder. If several entries are matched by the search key, most TCAMs return the index of the highest priority entry, i.e., the entry with the smallest index; and this type of ML encoder is called a priority encoder.
TCAM devices are increasingly used for performing high-speed packet classification, which is an essential component of many networking applications, such as routing, monitoring and security. For packet classification, routers use a classification database, which contains rules (sometimes called filters). Each rule specifies a certain pattern, which is typically based on certain packet header fields, such as the source/destination addresses, source/destination port numbers and protocol type, and an action to apply to the packets that match the pattern. The patterns are stored as entries in the TCAM.
Memory chips suffer from error events (often called soft errors), which may be caused by low-energy alpha particles, neutron hits, or cosmic rays. In a TCAM error event, a TCAM symbol can change its value to any symbol in {“0”, “1”, “*”}. The problem of soft errors in conventional random access memory (RAM) is typically handled by appending check symbols to the data according to some error-detecting or error-correcting code (ECC), and then applying an ECC check to each memory word upon access. This sort of solution is impractical in TCAM, however, since all entries are accessed in parallel.
Soft errors in the TCAM device can cause various types of matching errors: An error in a TCAM entry may result either in the entry rejecting a search key, even though it should have returned a match (a false miss), or in an entry matching a search key that it should have rejected (a false hit). Matching a search key with the wrong entry can have adverse effects on the packet classification process, since different entries have different actions associated with them in the rule database. As an example, such an error may cause malicious packets that should have been dropped for security reasons to be erroneously forwarded, or vice versa.